# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/20 0:43
@FileName      : 迷宫问题.py
@LastEditors   : None
@Editors       : PyCharm
“”“

”“”
回溯算法：回溯算法实际上一个类似枚举的搜索尝试过程，
主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
"""
# 初始化地图
maze = [['1', '0', '1', '1', '1'],
        ['1', '1', '1', '0', '1'],
        ['1', '0', '0', '1', '1'],
        ['1', '0', '0', '1', '0'],
        ['1', '0', '0', '1', '1']]


def maze_puzzle(maze, x, y):
    maze[y][x] = 'Y'
    if x == (len(maze[0]) - 1) and y == (len(maze) - 1):
        print_maze(maze)
    if canMove(maze, x + 1, y):
        maze_puzzle(maze, x + 1, y)
        maze[y][x + 1] = '1'
    if canMove(maze, x - 1, y):
        maze_puzzle(maze, x - 1, y)
        maze[y][x - 1] = '1'
    if canMove(maze, x, y + 1):
        maze_puzzle(maze, x, y + 1)
        maze[y + 1][x] = '1'
    if canMove(maze, x, y - 1):
        maze_puzzle(maze, x, y - 1)
        maze[y - 1][x] = '1'


def canMove(maze, x, y):
    return x >= 0 and y >= 0 and x < len(maze[0]) and y < len(maze) and maze[y][x] != 'Y' and maze[y][x] == '1'


def print_maze(maze):
    for i in maze:
        for j in i:
            print(j, end='')
        print()


maze_puzzle(maze, 0, 0)
